Evolutionary Computation in Routing (Using Genetic Algorithm)¶
Import¶
Importing the required packages
In [1]:
from abc import ABC, abstractmethod
from typing import Callable
import math
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import matplotlib.artist as artist
# import matplotlib.collections as collections
import IPython.display
plt.rcParams["animation.html"] = "jshtml"
Definition Common Methods¶
Distance Calculator¶
In [2]:
class Distance:
@classmethod
def simple(self, start: tuple[float, float], end: tuple[float, float]) -> float:
return (end[0] - start[0]) + (end[1] - start[1])
@classmethod
def euclidean_squared(self, start: tuple[float, float], end: tuple[float, float]) -> float:
"""
Calculates the squared Euclidean distance between two points in 2D space.
Parameters:
start (tuple[float, float]): The starting point.
end (tuple[float, float]): The ending point.
Returns:
float: The squared Euclidean distance between the two points.
"""
return ((end[0] - start[0]) ** 2) + ((end[1] - start[1]) ** 2)
@classmethod
def euclidean(self, start: tuple[float, float], end: tuple[float, float]) -> float:
"""
Calculates the Euclidean distance between two points in 2D space.
Parameters:
start (tuple[float, float]): The starting point.
end (tuple[float, float]): The ending point.
Returns:
float: The Euclidean distance between the two points.
"""
# return math.sqrt(euclidean_squared(start, end))
# return numpy.hypot(end[0] - start[0], end[1] - start[1])
return np.linalg.norm(np.array(start) - np.array(end))
Score Calculator¶
In [3]:
class Score:
@classmethod
def euclidean_sum(self, path: list[tuple[float, float]]) -> float:
return sum(Distance.euclidean(path[i], path[i+1]) for i in range(len(path)-1))
@classmethod
def euclidean_squaredSum(self, path: list[tuple[float, float]]) -> float:
return sum(Distance.euclidean_squared(path[i], path[i+1]) for i in range(len(path)-1))
Definition Scene Tools¶
Scene Generator¶
In [4]:
class SceneGenerator:
@classmethod
def grid(self, capacity: int, width: float, height: float, with_info: bool = False) -> tuple[float, float, int, list[list[tuple[float, float]]]] | list[tuple[float, float]]:
nodes: list[tuple[float, float]] = [(np.random.uniform(0, width), np.random.uniform(0, height)) for _ in range(capacity)]
if with_info:
return width, height, capacity, nodes
else:
return nodes
@classmethod
def grid_expand(self, capacity: int, width: float, height: float, expand: tuple[int, int] = (1, 1), with_info: bool = False) -> tuple[float, float, int, list[list[tuple[float, float]]]] | list[tuple[float, float]]:
nodes: list[tuple[float, float]] = [(width * expand_width + np.random.uniform(0, width), height * expand_height + np.random.uniform(0, width)) for _ in range(capacity) for expand_width in range(expand[0]) for expand_height in range(expand[1])]
if with_info:
width: float = width * expand[0]
height: float = height * expand[1]
capacity: int = capacity * expand[0] * expand[1]
return width, height, capacity, nodes
else:
return nodes
Scene Calculator¶
In [5]:
class SceneCalculator:
@classmethod
def occupied_area(self, width: float, height: float, number: int) -> float:
return width * height / number
@classmethod
def transmission_range(self, width: float, height: float, number: int, transmittable_number: int) -> float:
return math.sqrt(width * height * transmittable_number / (math.pi * number))
@classmethod
def transmission_area(self, transmission_range: float) -> float:
return math.pi * transmission_range ** 2
@classmethod
def transmittable_number(self, width: float, height: float, number: int, transmission_range: float) -> float:
return math.pi * transmission_range ** 2 * number / width * height
Algorithm¶
Abstract Algorithm¶
In [6]:
class DataDissemination(ABC):
def __init__(self, transmissionRange: float, distance: Callable[[tuple[float, float], tuple[float, float]], float] = Distance.euclidean) -> None:
"""
Parameters:
transmissionRange (float): The transmission range of each node.
distance (Callable[[tuple[float, float], tuple[float, float]], float]): A function that takes two nodes and returns the distance between them.
"""
self.transmissionRange: float = transmissionRange
self.distance: Callable[[tuple[float, float], tuple[float, float]], float] = distance
@abstractmethod
def route(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], getHistory: bool = False, verbose: bool = False) -> list[tuple[float, float]] | list[list[tuple[float, float]]]:
"""
find the path between two nodes in a graph.
Parameters:
nodes (list[tuple[float, float]]): A list of tuples representing the x and y coordinates of each node in the graph.
start (tuple[float, float]): The starting node of the path.
end (tuple[float, float]): The ending node of the path.
Returns:
list[tuple[float, float]]: A list of nodes that represent the path between the start and end nodes.
list[list[tuple[float, float]]]: A list of lists of nodes that represent the explore path.
"""
pass
Greedy Algorithm¶
In [7]:
class Greedy(DataDissemination):
"""
Selects transmittable nodes sequentially and records the current selection order,
if an invalid path is encountered, goes back to the previous node and reselects the next transmittable node.
"""
def __init__(self, transmissionRange: float, priority: Callable[[tuple[float, float], tuple[float, float]], float], distance: Callable[[tuple[float, float], tuple[float, float]], float] = Distance.euclidean) -> None:
"""
Parameters:
transmissionRange (float): The transmission range of each node.
priority (Callable[[tuple[float, float], tuple[float, float]], float]): Method of calculating the priority score of the selection.
distance (Callable[[tuple[float, float], tuple[float, float]], float]): A function that takes two nodes and returns the distance between them.
"""
super().__init__(transmissionRange, distance)
self.priority: Callable[[tuple[float, float], tuple[float, float]], float] = priority
def route(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], getHistory: bool = False, verbose: bool = False) -> list[tuple[float, float]] | list[list[tuple[float, float]]]:
path: list[tuple[float, float]] = [start]
priorityHistory: list[int] = []
history: list[list[tuple[float, float]]] = []
if getHistory: history.append(path.copy())
while path[-1] != end:
current_index: int = len(path)-1
current_node: tuple[float, float] = path[current_index]
transmittable: list[tuple[float, float]] = [node for node in nodes if self.distance(node, current_node) <= self.transmissionRange and node not in path and (current_node, node)]
if verbose: print(f"Greedy: route: current_node = ({current_node[0]:5.2f}, {current_node[1]:5.2f}) ; len(path) = {len(path):3} ; len(priorityHistory) = {len(priorityHistory):3} ; len(transmittable) = {len(transmittable):3}")
if len(transmittable) != 0:
if end in transmittable:
path.append(end)
elif len(path) == len(priorityHistory)+1:
priorityHistory.append(0)
next: tuple[float, float] = max(transmittable, key=lambda node: self.priority(node, current_node))
path.append(next)
elif len(path) == len(priorityHistory):
priorityHistory[current_index] += 1
if priorityHistory[current_index] < len(transmittable):
next: tuple[float, float] = sorted(transmittable, key=lambda node: self.priority(node, current_node))[priorityHistory[current_index]]
path.append(next)
else: # priorityHistory[current_index] == len(transmittable)
priorityHistory[current_index-1] += 1
priorityHistory = priorityHistory[0:current_index]
path = path[0:current_index]
else:
if current_index > 1: priorityHistory[current_index-1] += 1
priorityHistory = priorityHistory[0:current_index]
path = path[0:current_index]
if getHistory: history.append(path.copy())
if len(path) < 1: break
if getHistory:
return history
else:
return path
Randomized Algorithm¶
In [8]:
class Random(DataDissemination):
"""
Randomly selects a transmittable node and records the shuffled transmittable and the current selection order (otherwise the failed path cannot be discarded),
if an invalid path is encountered, go back to the previous node and reselect the next transmittable node.
"""
def route(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], getHistory: bool = False, verbose: bool = False) -> list[tuple[float, float]] | list[list[tuple[float, float]]]:
path: list[tuple[float, float]] = [start]
priorityHistory: list[int] = []
priorityRecords: list[list[tuple[float, float]]] = []
history: list[list[tuple[float, float]]] = []
if getHistory: history.append(path.copy())
while path[-1] != end:
current_index: int = len(path)-1
current_node: tuple[float, float] = path[current_index]
transmittable: list[tuple[float, float]] = [node for node in nodes if self.distance(node, current_node) <= self.transmissionRange and node not in path and (current_node, node)]
if verbose: print(f"Random: route: current_node = ({current_node[0]:5.2f}, {current_node[1]:5.2f}) ; len(path) = {len(path):3} ; len(priorityHistory) = {len(priorityHistory):3} ; len(transmittable) = {len(transmittable):3}")
if len(transmittable) != 0:
if end in transmittable:
path.append(end)
elif len(path) == len(priorityHistory)+1:
np.random.shuffle(transmittable)
priorityHistory.append(0)
priorityRecords.append(transmittable)
next: tuple[float, float] = transmittable[0]
path.append(next)
elif len(path) == len(priorityHistory):
priorityHistory[current_index] += 1
if priorityHistory[current_index] < len(transmittable):
next: tuple[float, float] = priorityRecords[-1][priorityHistory[-1]]
path.append(next)
else: # priorityHistory[current_index] == len(transmittable)
priorityHistory[current_index-1] += 1
priorityHistory = priorityHistory[0:current_index]
priorityRecords = priorityRecords[0:current_index]
path = path[0:current_index]
else:
if current_index > 1: priorityHistory[current_index-1] += 1
priorityHistory = priorityHistory[0:current_index]
priorityRecords = priorityRecords[0:current_index]
path = path[0:current_index]
if getHistory: history.append(path.copy())
if len(path) < 1: break
if getHistory:
return history
else:
return path
In [9]:
class Random_Retroactive(DataDissemination): # Warning: It is impossible to escape from a very short invalid path. It is recommended to record the exploration situation.
"""
Randomly selecting a transmittable node does not record any information,
if it encounters an invalid path, it returns to (discards the end of) the randomly length path and explores it again.
"""
def __init__(self, transmissionRange: float, retroactiveCeilingRate: float = 0.25, distance: Callable[[tuple[float, float], tuple[float, float]], float] = Distance.euclidean) -> None:
"""
Parameters:
transmissionRange (float): The transmission range of each node.
retroactiveCeilingRate (float): The rate at which retroactive nodes are added to the path. Default is 0.25.
distance (Callable[[tuple[float, float], tuple[float, float]], float]): A function that takes two nodes and returns the distance between them.
"""
super().__init__(transmissionRange, distance)
self.retroactiveCeilingRate: float = retroactiveCeilingRate
def route(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], getHistory: bool = False, verbose: bool = False) -> list[tuple[float, float]] | list[list[tuple[float, float]]]:
path: list[tuple[float, float]] = [start]
history: list[list[tuple[float, float]]] = []
if getHistory: history.append(path.copy())
while path[-1] != end:
current_index: int = len(path)-1
current_node: tuple[float, float] = path[current_index]
transmittable: list[tuple[float, float]] = [node for node in nodes if self.distance(node, current_node) <= self.transmissionRange and node not in path and (current_node, node)]
if verbose: print(f"Random_Retroactive: route: current_node = ({current_node[0]:5.2f}, {current_node[1]:5.2f}) ; len(path) = {len(path):5} ; len(transmittable) = {len(transmittable):5}")
if len(transmittable) != 0:
next: tuple[float, float] = transmittable[np.random.randint(len(transmittable))]
path.append(next)
elif int(current_index*self.retroactiveCeilingRate) < 1:
path = path[0:current_index]
else:
retroactive: int = np.random.randint(0, int(current_index*self.retroactiveCeilingRate))
path = path[0:current_index-retroactive]
if getHistory: history.append(path.copy())
if verbose: print(path)
if getHistory:
return history
else:
return path
Genetic Algorithm¶
In [10]:
class Genetic(DataDissemination):
def __init__(self, transmissionRange: float,
crossoverRate: float, mutationRate: float, populationSize: int, generations: int,
generator: DataDissemination, fitness: Callable[[list[tuple[float, float]]], float],
distance: Callable[[tuple[float, float], tuple[float, float]], float] = Distance.euclidean) -> None:
"""
Parameters:
transmissionRange (float): The transmission range of each node.
crossoverRate (float): The rate at which crossover is performed.
mutationRate (float): The rate at which mutation is performed.
populationSize (int): The size of the population.
generations (int): The number of generations to evolve.
generator (DataDissemination): The generator object.
fitness (Callable[[list[tuple[float, float]]], float]): A function that takes a path and returns its fitness.
distance (Callable[[tuple[float, float], tuple[float, float]], float]): A function that takes two nodes and returns the distance between them. Defaults to euclidean distance.
"""
super().__init__(transmissionRange, distance)
self.crossoverRate: float = crossoverRate
self.mutationRate: float = mutationRate
self.populationSize: int = populationSize
self.generations: int = generations
self.generator: DataDissemination = generator
self.fitness: Callable[[list[tuple[float, float]]], float] = fitness
def generate_initial_population(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], verbose: bool = False) -> list[list[tuple[float, float]]]:
"""
Generates the initial population of paths for the genetic algorithm.
Parameters:
start (tuple[float, float]): The starting node of each path.
end (tuple[float, float]): The ending node of each path.
verbose (bool):
This method initializes the population by generating routes using a random algorithm and appends them to the path list.
Each route starts at the given start node and ends at the given end node.
"""
if verbose: print(f"Genetic: Generating initial population")
pathList: list[list[tuple[float, float]]] = []
for i in range(self.populationSize):
path = self.generator.route(nodes, start, end)
if len(path) > 0 and path[0] == start and path[-1] == end: pathList.append(path)
if verbose: print(f"Genetic: Generate path {i+1:3} | fitness: {self.fitness(pathList[i])}")
return pathList
def crossover(self, path1: list[tuple[float, float]], path2: list[tuple[float, float]]) -> list[list[tuple[float, float]]]:
# Find an intersection other than the starting point and the end point
"""
Applies crossover to two paths to produce two new paths.
Parameters:
path1 (list[tuple[float, float]]): The first path.
path2 (list[tuple[float, float]]): The second path.
Returns:
list[list[tuple[float, float]]]: A list of two new paths produced by the crossover operation, or an empty list if no crossover is possible.
This method finds an intersection other than the starting point and the end point, and if there is one, it shuffles the intersection points and does a crossover at each one. If there is no intersection, it returns an empty list.
"""
intersection: list[tuple[float, float]] = list(set(path1[1:-1]) & set(path2[1:-1]))
if len(intersection) > 0:
np.random.shuffle(intersection)
for i in range(len(intersection)):
path1_front: list[tuple[float, float]] = path1[:path1.index(intersection[i])]
path2_front: list[tuple[float, float]] = path2[:path2.index(intersection[i])]
path1_back: list[tuple[float, float]] = path1[path1.index(intersection[i]):]
path2_back: list[tuple[float, float]] = path2[path2.index(intersection[i]):]
if path1_front != path2_front and path1_back != path2_back:
return [path1_front + path2_back, path2_front + path1_back]
return []
def mutation(self, nodes: list[tuple[float, float]], path: list[tuple[float, float]]) -> list[tuple[float, float]]:
"""
Applies mutation to a path to produce a new path.
Parameters:
path (list[tuple[float, float]]): The path to mutate.
Returns:
list[tuple[float, float]]: A new path produced by the mutation operation.
This method randomly finds two nodes in the path and replaces the segment between them with a new segment generated using a random algorithm. The new path is then returned.
"""
# Randomly find two nodes in a path
node_list: list[tuple[float, float]] = path.copy()
if len(node_list) > 2:
node1: tuple[float, float]
node2: tuple[float, float]
np.random.shuffle(node_list)
node1, node2 = node_list[:2]
# Make sure node1 is in front of node2, otherwise swap
if path.index(node1) > path.index(node2):
node1, node2 = node2, node1
# Generate a new segment between node1 and node2
transmittable: list[tuple[float, float]] = list(set(nodes) - (set(path[:path.index(node1)]) | set(path[path.index(node2):])) | {node1, node2})
subPath: list[tuple[float, float]] = self.generator.route(transmittable, node1, node2)
if len(subPath) > 0:
# Replace the segments from node1 to node2 in path with subPath and return them
return path[:path.index(node1)] + subPath + path[path.index(node2)+1:]
return []
def route(self, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], getHistory: bool = False, verbose: bool = False) -> list[tuple[float, float]] | list[list[tuple[float, float]]]:
"""
Calculates the shortest path between two nodes in a graph using a genetic algorithm.
Parameters:
start (tuple[float, float]): The starting node of the path.
end (tuple[float, float]): The ending node of the path.
generations (int | None): The number of generations to run the genetic algorithm. If None, it will run for len(nodes) ** 2 generations. Defaults to None.
Returns:
list[tuple[float, float]]: A list of nodes that represent the shortest path between the start and end nodes.
This method starts by generating an initial population of paths using a random algorithm. It then iteratively applies crossover and mutation operations to the population for a specified number of generations. The fittest path is then returned.
"""
pathList: list[list[tuple[float, float]]] = self.generate_initial_population(nodes, start, end, verbose)
pathList.sort(key=self.fitness)
history: list[list[tuple[float, float]]] = []
if getHistory: history.append(pathList[0].copy())
if verbose: print(f"Genetic: Generation {0:3} : Best fitness: {self.fitness(pathList[0])}")
for generation in range(self.generations):
for i in range(self.populationSize):
# if verbose: print(f" : fitness(population[{i:3}]) = {self.fitness(pathList[i])}")
if np.random.random() < self.crossoverRate:
otherIndex: int = i
while otherIndex == i:
otherIndex = np.random.randint(0, self.populationSize)
path1: list[tuple[float, float]] = pathList[i]
path2: list[tuple[float, float]] = pathList[otherIndex]
newPaths: list[list[tuple[float, float]]] = self.crossover(path1, path2)
if newPaths:
for newPath in newPaths:
if len(newPath) > 0 and newPath[0] == start and newPath[-1] == end: pathList.append(newPath)
if np.random.random() < self.mutationRate:
newPath = self.mutation(nodes, pathList[i])
if len(newPath) > 0 and newPath[0] == start and newPath[-1] == end: pathList.append(newPath)
pathList.sort(key=self.fitness)
pathList = pathList[:self.populationSize]
if getHistory: history.append(pathList[0].copy())
if verbose: print(f"Genetic: Generation {generation+1:3} : Best fitness: {self.fitness(pathList[0])}")
if getHistory:
return history
else:
return pathList[0]
Simulator¶
In [11]:
class Simulator:
def __init__(self, width: float, height: float, nodes: list[tuple[float, float]], start: tuple[float, float], end: tuple[float, float], figureSize: tuple[float, float] = (5, 5)):
self.width: float = width
self.height: float = height
self.nodes: list[tuple[float, float]] = nodes
self.start: tuple[float, float] = start
self.end: tuple[float, float] = end
self.point_size = ((width * height) / len(nodes))
self.figure: plt.Figure
self.axes: plt.Axes
self.figure, self.axes = plt.subplots(1, 1, figsize = figureSize)
def execution(self, algorithm: DataDissemination, title: str, withHistory: bool = False, verbose: bool = False) -> list[artist.Artist]:
self.axes.clear()
self.axes.set_title(title)
self.axes.set_xlabel("x")
self.axes.set_ylabel("y")
self.axes.set_xlim(0, self.width)
self.axes.set_ylim(0, self.height)
self.axes.grid(True)
artists: list[artist.Artist] = []
if withHistory:
history: list[list[tuple[float, float]]] = algorithm.route(self.nodes, self.start, self.end, getHistory=True, verbose=verbose)
for path in history:
frame: list[artist.Artist] = self.axes.plot(*zip(*path), color="red")
frame.append(self.axes.scatter(*zip(*self.nodes), [self.point_size for _ in self.nodes], c="black"))
artists.append(frame)
print(f"{title}: Sum of squared distances of path: {Score.euclidean_squaredSum(history[-1])}")
artistAnimation = animation.ArtistAnimation(fig=self.figure, artists=artists, interval=5)
artistAnimation.save(f"{title}.gif")
IPython.display.display(artistAnimation)
else:
path: list[tuple[float, float]] = algorithm.route(self.nodes, self.start, self.end, verbose=verbose)
frame: list[artist.Artist] = self.axes.plot(*zip(*path), color="red")
frame.append(self.axes.scatter(*zip(*self.nodes), [self.point_size for _ in self.nodes], c="black"))
artists.append(frame)
print(f"{title}: Sum of squared distances of path: {Score.euclidean_squaredSum(path)}")
self.figure.savefig(fname=f"{title}.png")
IPython.display.display(self.figure)
return artists
Simulation¶
Construction of Environment and Simulator¶
In [12]:
np.random.seed(202411)
grid_capacity: int = 1
grid_width: float = 10
grid_height: float = 10
grid_expand: tuple[int, int] = (10, 10)
width: float # = grid_width * grid_expand[0]
height: float # = grid_height * grid_expand[1]
node_number: int # = grid_capacity * grid_expand[0] * grid_expand[1]
nodes: list[tuple[float, float]]
# width, height, node_number, nodes = SceneGenerator.grid(grid_capacity, grid_width, grid_height, True)
width, height, node_number, nodes = SceneGenerator.grid_expand(grid_capacity, grid_width, grid_height, grid_expand, True)
node_transmission_number = 9
node_transmission_range: float = SceneCalculator.transmission_range(width, height, node_number, node_transmission_number)
node_transmission_area: float = SceneCalculator.transmission_area(node_transmission_range)
node_occupied_area: float = SceneCalculator.occupied_area(width, height, node_number)
print(f"node occupied area: map_width * map_height / node_number = {width} * {height} / {node_number} = {node_occupied_area}")
print(f"node transmission range:")
print(f" transmission number: {node_transmission_number}")
print(f" transmission range: math.sqrt(occupied_area * transmission_number / math.pi) = math.sqrt({node_occupied_area} * {node_transmission_number} / {math.pi}) = {node_transmission_range}")
print(f" transmission area: math.pi * transmission_range ^ 2 = {math.pi} * {node_transmission_range} ^ 2 = {node_transmission_area}")
sum_number: int = 0
for index, node in enumerate(nodes):
sum_number += len([1 for other in nodes if Distance.euclidean(node, other) <= node_transmission_range])
print(f"average transmission number: sum_number / node_number = {sum_number} / {node_number} = {sum_number / node_number}")
startIndex, endIndex = np.random.choice(range(node_number), 2, False)
print(f"start: nodes[{startIndex}]: {nodes[startIndex]}\nend: nodes[{endIndex}]: {nodes[endIndex]}")
figureSize: tuple[float, float] = (10, 10)
simulator = Simulator(width, height, nodes, nodes[startIndex], nodes[endIndex], figureSize)
node occupied area: map_width * map_height / node_number = 100 * 100 / 100 = 100.0 node transmission range: transmission number: 9 transmission range: math.sqrt(occupied_area * transmission_number / math.pi) = math.sqrt(100.0 * 9 / 3.141592653589793) = 16.925687506432688 transmission area: math.pi * transmission_range ^ 2 = 3.141592653589793 * 16.925687506432688 ^ 2 = 899.9999999999998 average transmission number: sum_number / node_number = 790 / 100 = 7.9 start: nodes[97]: (98.53512714743789, 77.68036102493139) end: nodes[42]: (40.548556730733225, 24.237129396007624)
Constructing Algorithms and Executing Routes¶
In [13]:
greedy = Greedy(node_transmission_range, Distance.euclidean_squared)
artists: list[artist.Artist] = simulator.execution(greedy, "Greedy Algorithm", True, True)
Greedy: route: current_node = (98.54, 77.68) ; len(path) = 1 ; len(priorityHistory) = 0 ; len(transmittable) = 2 Greedy: route: current_node = (92.90, 92.26) ; len(path) = 2 ; len(priorityHistory) = 1 ; len(transmittable) = 3 Greedy: route: current_node = (82.55, 86.44) ; len(path) = 3 ; len(priorityHistory) = 2 ; len(transmittable) = 7 Greedy: route: current_node = (97.75, 85.72) ; len(path) = 4 ; len(priorityHistory) = 3 ; len(transmittable) = 0 Greedy: route: current_node = (82.55, 86.44) ; len(path) = 3 ; len(priorityHistory) = 3 ; len(transmittable) = 7 Greedy: route: current_node = (72.81, 80.31) ; len(path) = 4 ; len(priorityHistory) = 3 ; len(transmittable) = 9 Greedy: route: current_node = (66.26, 65.01) ; len(path) = 5 ; len(priorityHistory) = 4 ; len(transmittable) = 8 Greedy: route: current_node = (63.83, 48.43) ; len(path) = 6 ; len(priorityHistory) = 5 ; len(transmittable) = 8 Greedy: route: current_node = (49.20, 55.59) ; len(path) = 7 ; len(priorityHistory) = 6 ; len(transmittable) = 7 Greedy: route: current_node = (64.08, 50.76) ; len(path) = 8 ; len(priorityHistory) = 7 ; len(transmittable) = 6 Greedy: route: current_node = (57.48, 66.31) ; len(path) = 9 ; len(priorityHistory) = 8 ; len(transmittable) = 5 Greedy: route: current_node = (49.60, 79.34) ; len(path) = 10 ; len(priorityHistory) = 9 ; len(transmittable) = 9 Greedy: route: current_node = (44.16, 63.79) ; len(path) = 11 ; len(priorityHistory) = 10 ; len(transmittable) = 5 Greedy: route: current_node = (51.94, 48.96) ; len(path) = 12 ; len(priorityHistory) = 11 ; len(transmittable) = 4 Greedy: route: current_node = (47.42, 33.52) ; len(path) = 13 ; len(priorityHistory) = 12 ; len(transmittable) = 7 Greedy Algorithm: Sum of squared distances of path: 3047.035973703784
In [14]:
random = Random(node_transmission_range)
artists: list[artist.Artist] = simulator.execution(random, "Randomized Algorithm", True, True)
Random: route: current_node = (98.54, 77.68) ; len(path) = 1 ; len(priorityHistory) = 0 ; len(transmittable) = 2 Random: route: current_node = (97.75, 85.72) ; len(path) = 2 ; len(priorityHistory) = 1 ; len(transmittable) = 2 Random: route: current_node = (82.55, 86.44) ; len(path) = 3 ; len(priorityHistory) = 2 ; len(transmittable) = 7 Random: route: current_node = (92.90, 92.26) ; len(path) = 4 ; len(priorityHistory) = 3 ; len(transmittable) = 1 Random: route: current_node = (81.22, 92.91) ; len(path) = 5 ; len(priorityHistory) = 4 ; len(transmittable) = 5 Random: route: current_node = (65.84, 95.10) ; len(path) = 6 ; len(priorityHistory) = 5 ; len(transmittable) = 5 Random: route: current_node = (68.20, 83.86) ; len(path) = 7 ; len(priorityHistory) = 6 ; len(transmittable) = 9 Random: route: current_node = (80.76, 78.01) ; len(path) = 8 ; len(priorityHistory) = 7 ; len(transmittable) = 4 Random: route: current_node = (85.33, 66.31) ; len(path) = 9 ; len(priorityHistory) = 8 ; len(transmittable) = 5 Random: route: current_node = (98.95, 59.30) ; len(path) = 10 ; len(priorityHistory) = 9 ; len(transmittable) = 3 Random: route: current_node = (86.00, 57.81) ; len(path) = 11 ; len(priorityHistory) = 10 ; len(transmittable) = 5 Random: route: current_node = (88.13, 42.41) ; len(path) = 12 ; len(priorityHistory) = 11 ; len(transmittable) = 6 Random: route: current_node = (94.97, 28.63) ; len(path) = 13 ; len(priorityHistory) = 12 ; len(transmittable) = 4 Random: route: current_node = (96.75, 14.63) ; len(path) = 14 ; len(priorityHistory) = 13 ; len(transmittable) = 3 Random: route: current_node = (80.51, 12.09) ; len(path) = 15 ; len(priorityHistory) = 14 ; len(transmittable) = 6 Random: route: current_node = (72.59, 18.56) ; len(path) = 16 ; len(priorityHistory) = 15 ; len(transmittable) = 9 Random: route: current_node = (59.11, 12.06) ; len(path) = 17 ; len(priorityHistory) = 16 ; len(transmittable) = 8 Random: route: current_node = (45.03, 15.83) ; len(path) = 18 ; len(priorityHistory) = 17 ; len(transmittable) = 6 Randomized Algorithm: Sum of squared distances of path: 3281.706879734897
In [15]:
genetic = Genetic(node_transmission_range, 0.25, 0.25, 15, 100, Random(node_transmission_range), Score.euclidean_squaredSum)
artists: list[artist.Artist] = simulator.execution(genetic, "Genetic Algorithm", True, True)
Genetic: Generating initial population Genetic: Generate path 1 | fitness: 3851.449203042813 Genetic: Generate path 2 | fitness: 4955.270760947289 Genetic: Generate path 3 | fitness: 4267.010406628992 Genetic: Generate path 4 | fitness: 3100.748960550383 Genetic: Generate path 5 | fitness: 7567.763948328392 Genetic: Generate path 6 | fitness: 3546.84839546297 Genetic: Generate path 7 | fitness: 6454.719911250608 Genetic: Generate path 8 | fitness: 2620.6019436786855 Genetic: Generate path 9 | fitness: 5069.346571479841 Genetic: Generate path 10 | fitness: 4731.006925657799 Genetic: Generate path 11 | fitness: 8412.673581440715 Genetic: Generate path 12 | fitness: 3392.0912582719393 Genetic: Generate path 13 | fitness: 7332.848380859071 Genetic: Generate path 14 | fitness: 4442.924494479132 Genetic: Generate path 15 | fitness: 1976.0932377690283 Genetic: Generation 0 : Best fitness: 1976.0932377690283 Genetic: Generation 1 : Best fitness: 1976.0932377690283 Genetic: Generation 2 : Best fitness: 1976.0932377690283 Genetic: Generation 3 : Best fitness: 1976.0932377690283 Genetic: Generation 4 : Best fitness: 1778.508076265432 Genetic: Generation 5 : Best fitness: 1778.508076265432 Genetic: Generation 6 : Best fitness: 1778.508076265432 Genetic: Generation 7 : Best fitness: 1689.6923629817475 Genetic: Generation 8 : Best fitness: 1689.6923629817475 Genetic: Generation 9 : Best fitness: 1689.6923629817475 Genetic: Generation 10 : Best fitness: 1689.6923629817475 Genetic: Generation 11 : Best fitness: 1689.6923629817475 Genetic: Generation 12 : Best fitness: 1552.8605952013281 Genetic: Generation 13 : Best fitness: 1552.8605952013281 Genetic: Generation 14 : Best fitness: 1552.8605952013281 Genetic: Generation 15 : Best fitness: 1552.8605952013281 Genetic: Generation 16 : Best fitness: 1401.4601338818777 Genetic: Generation 17 : Best fitness: 1401.4601338818777 Genetic: Generation 18 : Best fitness: 1401.4601338818777 Genetic: Generation 19 : Best fitness: 1401.4601338818777 Genetic: Generation 20 : Best fitness: 1389.752542534256 Genetic: Generation 21 : Best fitness: 1389.752542534256 Genetic: Generation 22 : Best fitness: 1389.752542534256 Genetic: Generation 23 : Best fitness: 1389.752542534256 Genetic: Generation 24 : Best fitness: 1357.9699990323898 Genetic: Generation 25 : Best fitness: 1357.9699990323898 Genetic: Generation 26 : Best fitness: 1357.9699990323898 Genetic: Generation 27 : Best fitness: 1357.9699990323898 Genetic: Generation 28 : Best fitness: 1357.9699990323898 Genetic: Generation 29 : Best fitness: 1357.9699990323898 Genetic: Generation 30 : Best fitness: 1357.9699990323898 Genetic: Generation 31 : Best fitness: 1357.9699990323898 Genetic: Generation 32 : Best fitness: 1357.9699990323898 Genetic: Generation 33 : Best fitness: 1357.9699990323898 Genetic: Generation 34 : Best fitness: 1357.9699990323898 Genetic: Generation 35 : Best fitness: 1357.9699990323898 Genetic: Generation 36 : Best fitness: 1357.9699990323898 Genetic: Generation 37 : Best fitness: 1357.9699990323898 Genetic: Generation 38 : Best fitness: 1357.9699990323898 Genetic: Generation 39 : Best fitness: 1333.9159512384326 Genetic: Generation 40 : Best fitness: 1333.9159512384326 Genetic: Generation 41 : Best fitness: 1333.9159512384326 Genetic: Generation 42 : Best fitness: 1333.9159512384326 Genetic: Generation 43 : Best fitness: 1333.9159512384326 Genetic: Generation 44 : Best fitness: 1333.9159512384326 Genetic: Generation 45 : Best fitness: 1333.9159512384326 Genetic: Generation 46 : Best fitness: 1333.9159512384326 Genetic: Generation 47 : Best fitness: 1333.9159512384326 Genetic: Generation 48 : Best fitness: 1333.9159512384326 Genetic: Generation 49 : Best fitness: 1333.9159512384326 Genetic: Generation 50 : Best fitness: 1333.9159512384326 Genetic: Generation 51 : Best fitness: 1333.9159512384326 Genetic: Generation 52 : Best fitness: 1333.9159512384326 Genetic: Generation 53 : Best fitness: 1333.9159512384326 Genetic: Generation 54 : Best fitness: 1261.6340748166842 Genetic: Generation 55 : Best fitness: 1261.6340748166842 Genetic: Generation 56 : Best fitness: 1261.6340748166842 Genetic: Generation 57 : Best fitness: 1261.6340748166842 Genetic: Generation 58 : Best fitness: 1261.6340748166842 Genetic: Generation 59 : Best fitness: 1237.5800270227273 Genetic: Generation 60 : Best fitness: 1237.5800270227273 Genetic: Generation 61 : Best fitness: 1237.5800270227273 Genetic: Generation 62 : Best fitness: 1237.5800270227273 Genetic: Generation 63 : Best fitness: 1237.5800270227273 Genetic: Generation 64 : Best fitness: 1237.5800270227273 Genetic: Generation 65 : Best fitness: 1237.5800270227273 Genetic: Generation 66 : Best fitness: 1237.5800270227273 Genetic: Generation 67 : Best fitness: 1237.5800270227273 Genetic: Generation 68 : Best fitness: 1237.5800270227273 Genetic: Generation 69 : Best fitness: 1237.5800270227273 Genetic: Generation 70 : Best fitness: 1237.5800270227273 Genetic: Generation 71 : Best fitness: 1237.5800270227273 Genetic: Generation 72 : Best fitness: 1237.5800270227273 Genetic: Generation 73 : Best fitness: 1237.5800270227273 Genetic: Generation 74 : Best fitness: 1237.5800270227273 Genetic: Generation 75 : Best fitness: 1237.5800270227273 Genetic: Generation 76 : Best fitness: 1237.5800270227273 Genetic: Generation 77 : Best fitness: 1237.5800270227273 Genetic: Generation 78 : Best fitness: 1237.5800270227273 Genetic: Generation 79 : Best fitness: 1237.5800270227273 Genetic: Generation 80 : Best fitness: 1237.5800270227273 Genetic: Generation 81 : Best fitness: 1237.5800270227273 Genetic: Generation 82 : Best fitness: 1237.5800270227273 Genetic: Generation 83 : Best fitness: 1237.5800270227273 Genetic: Generation 84 : Best fitness: 1237.5800270227273 Genetic: Generation 85 : Best fitness: 1237.5800270227273 Genetic: Generation 86 : Best fitness: 1237.5800270227273 Genetic: Generation 87 : Best fitness: 1237.5800270227273 Genetic: Generation 88 : Best fitness: 1237.5800270227273 Genetic: Generation 89 : Best fitness: 1237.5800270227273 Genetic: Generation 90 : Best fitness: 1237.5800270227273 Genetic: Generation 91 : Best fitness: 1237.5800270227273 Genetic: Generation 92 : Best fitness: 1237.5800270227273 Genetic: Generation 93 : Best fitness: 1237.5800270227273 Genetic: Generation 94 : Best fitness: 1237.5800270227273 Genetic: Generation 95 : Best fitness: 1237.5800270227273 Genetic: Generation 96 : Best fitness: 1237.5800270227273 Genetic: Generation 97 : Best fitness: 1237.5800270227273 Genetic: Generation 98 : Best fitness: 1237.5800270227273 Genetic: Generation 99 : Best fitness: 1237.5800270227273 Genetic: Generation 100 : Best fitness: 1237.5800270227273 Genetic Algorithm: Sum of squared distances of path: 1237.5800270227273